package backend.alloctor;

import Utils.Edge;
import backend.Instruction.*;
import backend.component.RISCVblock;
import backend.component.RISCVfunction;
import backend.Instruction.RISCVinst;
import backend.component.RISCVimm;
import backend.component.RISCVmodule;
import backend.Register.*;
import midend.IR_Value.IR_BaseBlock;

import java.util.*;

import static backend.Register.initReg.phyRegs;
import static backend.Register.initReg.phyfRegs;

public class GraphColoring_RegisterAllocator {

    private RISCVmodule riscVmodule;

    //变量的 UD 链 DU链 以及活跃变量分析
    private final HashMap<RISCVblock, LinkedList<RISCVreg>> UseReg = new HashMap<>();
    private final HashMap<RISCVblock, LinkedList<RISCVreg>> DefReg = new HashMap<>();
    private final HashMap<RISCVblock, LinkedList<RISCVreg>> liveInsReg = new HashMap<>();
    private final HashMap<RISCVblock, LinkedList<RISCVreg>> liveOutsReg = new HashMap<>();

    // 溢出的变量
    private final HashSet<RISCVoperand> spillWorkList = new HashSet<>();

    //可以简化的节点的列表
    private final HashSet<RISCVoperand> simWorkList = new HashSet<>();
    private final HashSet<RISCVoperand> spilledNodes = new HashSet<>();

    //存储基本块中的 局部寄存器之间的冲突关系
    private final HashMap<RISCVblock, LinkedList<LinkedList<RISCVreg>>> blockLocalInterfere = new HashMap<>();
    private final HashSet<RISCVoperand> allOperands = new HashSet<>();
    private final HashMap<RISCVoperand, HashSet<RISCVoperand>> adjList = new HashMap<>();

    //存储 冲突图的度数信息
    private final HashMap<RISCVoperand, Integer> degree = new HashMap<>();
    private final HashMap<RISCVoperand, Integer> spillWeight = new HashMap<>();
    private final HashSet<Edge<RISCVoperand, RISCVoperand>> adjSet = new HashSet<>();

    // 10 - 17用于函数调用的时候进行传递参数和返回值使用
    private final static int indexMinA = 10;
    private final static int indexMaxA = 17;

    //常量定义
    private final static String ST = "ST";
    private final static String All = "all";
    private final static String Other = "other";
    private final static String Lin = "livein";
    private final static String Lout = "liveout";

    //寄存器分配的时候栈溢出 的处理 以及染色信息
    private final Stack<RISCVoperand> stackForSelect = new Stack<>();
    private final HashSet<RISCVoperand> coloredNodes = new HashSet<>();
    private final HashMap<RISCVoperand, Integer> color = new HashMap<>();
    private final ArrayList<RISCVblock> hasBeenDfs = new ArrayList<>();

    //存储可分配的寄存器
    private final HashMap<RISCVfunction, Integer> maxUsePhyA = new HashMap<>();
    private final HashMap<RISCVfunction, Integer> maxUseFPhyA = new HashMap<>();

    //存储不同情况下 的  S/T，依据是否是第一阶段判断
    //S集合(SOperands)：跨函数调用时需保存的寄存器（调用后仍活跃）
    //T集合(TOperands)：临时寄存器（调用后不活跃，无需保存）
    private final HashSet<RISCVoperand> SOperands = new HashSet<>();
    private final HashSet<RISCVoperand> TOperands = new HashSet<>();


    // 存储函数的堆栈大小
    private final HashMap<RISCVfunction, Integer> funcStack;

    private static int tmpi = 0;

    public GraphColoring_RegisterAllocator(RISCVmodule riscVmodule) {
        this.riscVmodule = riscVmodule;
        this.funcStack = new HashMap<>() ;
        for (RISCVfunction functions : riscVmodule.getFunctions()) {
            int stackSize = functions.getStacksize();
            funcStack.put(functions, stackSize);
        }
    }


    private void initregs(){
        for(RISCVfunction riscVfunction:riscVmodule.getFunctions()){
            // 初始化基本块的寄存器集合 初始化所有的 UD DU liveIn liveOut
            for(RISCVblock block:riscVfunction.getBlocks()){
                UseReg.put(block,new LinkedList<>());
                DefReg.put(block,new LinkedList<>());
                liveInsReg.put(block,new LinkedList<>());
                liveOutsReg.put(block,new LinkedList<>());
                blockLocalInterfere.put(block,new LinkedList<>());
            }
        }
    }

    // 清除基本块中指定类型的寄存器集合
    private void blockClearRegs(RISCVblock block,String type){
        switch (type){
            case All:
                UseReg.get(block).clear();
                DefReg.get(block).clear();
                liveInsReg.get(block).clear();
                liveOutsReg.get(block).clear();
                blockLocalInterfere.get(block).clear();
                break;
            case Lin:
                // 仅清除 livein 寄存器集合
                liveInsReg.get(block).clear();
                break;
            case Lout:
                // 仅清除 liveout 寄存器集合
                liveOutsReg.get(block).clear();
                break;
        }
    }

    private boolean containsReg(RISCVblock block,RISCVreg reg){
        //当寄存器既不在 又不在  都不存在的时候才是 真
        return !(UseReg.get(block).contains(reg)) && !(DefReg.get(block).contains(reg));
    }

    public void run(){
        initregs();
        // 遍历所有函数，进行两次处理 一次浮点数寄存器分配，一次整数寄存器分配
        for (RISCVfunction riscVfunction : riscVmodule.getFunctions()) {
            // 第一次处理：优先处理浮点寄存器
            procedure(riscVfunction, true);
            finalAllocate(riscVfunction, true);

            // 预留特殊寄存器
            if(!"main".equals(riscVfunction.getName())) {
                riscVfunction.reserveSRegs(true);
            }
            RISCVinst riscVinst = riscVfunction.getFirstBlock().getInstructionlist().getFirst();

            //System.out.println(riscVinst + "  " + riscVfunction.isBig());
            if(riscVfunction.isBig()){
                ((RISCVmove)riscVinst).setSrc(new RISCVimm(-riscVfunction.getStacksize(),false));
            }
            else{
                ((RISCVbinary)riscVinst).setSrcRight(new RISCVimm(-riscVfunction.getStacksize(),true));
            }
        }
        // 再次遍历所有函数，进行第二次处理
        for (RISCVfunction riscVfunction : riscVmodule.getFunctions()) {
            // 第二次处理：不考虑浮点寄存器
            procedure(riscVfunction, false);
            finalAllocate(riscVfunction, false);

            //预留特殊寄存器
            if(!"main".equals(riscVfunction.getName())) {
                riscVfunction.reserveSRegs(false);
            }
            RISCVinst riscVinst = riscVfunction.getFirstBlock().getInstructionlist().getFirst();
            if(riscVfunction.isBig()){
                ((RISCVmove)riscVinst).setSrc(new RISCVimm(-riscVfunction.getStacksize(),false));
            }
            else{
                ((RISCVbinary)riscVinst).setSrcRight(new RISCVimm(-riscVfunction.getStacksize(),true));
            }
        }

        //寄存器分配完成之后进行的后续处理
        // 额外的寄存器分配后处理器，用于对分配后的寄存器做一些优化
        resetStackSize();
        for (RISCVfunction objFunction : riscVmodule.getFunctions()) {
            objFunction.instAlignStack(funcStack.get(objFunction));
        }
    }

    private void resetStackSize() {
        // 遍历 RISCV 模块中的所有函数
        for (RISCVfunction objFunction : riscVmodule.getFunctions()) {
            // 获取函数第一个代码块的第一条指令
            RISCVinst first_inst = objFunction.getFirstBlock().getInstructionlist().getFirst();
            // 调用 helpResetStack 方法重置第一个指令的栈大小
            helpResetStack(objFunction, first_inst, true);

            // 获取函数退出块的倒数第二条指令
            RISCVinst last2inst = getPreInstr(objFunction.getExitBlock().getInstructionlist().getLast(), objFunction.getExitBlock().getInstructionlist());
            // 调用 helpResetStack 方法重置倒数第二条指令的栈大小
            helpResetStack(objFunction, last2inst, false);
        }
    }

    private void helpResetStack(RISCVfunction objFunction, RISCVinst instr, boolean isFirst) {
        // 根据是否是第一个指令，计算栈大小的立即数
        int immediate;
        if (isFirst) {
            immediate = -objFunction.getStacksize();  // 第一个指令使用负的栈大小
        } else {
            immediate = objFunction.getStacksize();   // 非第一个指令使用正的栈大小
        }

        // 检查指令是否为二元操作指令（例如加法或减法）
        if (instr instanceof RISCVbinary) {
            // 如果立即数在 12 位有符号整数范围内
            if (2047 >= immediate && -2048 <= immediate) {
                // 直接将立即数设置为指令的右操作数
                ((RISCVbinary) instr).setSrcRight(new RISCVimm(immediate, true));
            } else {
                // 如果立即数太大，使用寄存器来存储该值
                objFunction.setBig(true);
                // 创建一个移动指令，将立即数加载到一个寄存器（此处为 phyRegs.get(5)）t0
                RISCVmove move = new RISCVmove(Arrays.asList(phyRegs.get(5), new RISCVimm(immediate, false)));
                // 在当前二元操作指令之前插入此移动指令
                objFunction.addInstBefore(instr, move);
                // 将寄存器值设置为二元操作指令的右操作数
                ((RISCVbinary) instr).setSrcRight(phyRegs.get(5));
            }
        }
    }

    public void clear(String type) {
        switch (type) {
            case ST -> {
                SOperands.clear();
                TOperands.clear();
            }
            //只清空工作表、着色信息，
            case Other -> {
                simWorkList.clear();
                spillWorkList.clear();
                spilledNodes.clear();
                coloredNodes.clear();
                stackForSelect.clear();
                color.clear();
            }
            case All -> {
                SOperands.clear();
                TOperands.clear();
                allOperands.clear();
                adjList.clear();
                adjSet.clear();
                simWorkList.clear();
                spillWorkList.clear();
                spilledNodes.clear();
                coloredNodes.clear();
                stackForSelect.clear();
                degree.clear();
                color.clear();
            }
        }
    }


    //记录的是可以使用的寄存器数量， 比如 t 寄存器 s 寄存器，依据需求适当调整
    private int K;


    public void procedure(RISCVfunction riscVfunction,boolean isfloat){
        clear(All);
        // 分析活跃变量（是否使用浮点寄存器）
        analyzeLive(riscVfunction, isfloat);
        // 默认可使用的 寄存器的数量是 12 个，减少对于硬件寄存器的使用量
        K=12;

        buildAndProcessGraph(riscVfunction,isfloat,true);

        // 如果有溢出的节点，重写程序并递归处理
        if (!spilledNodes.isEmpty()) {
            rewriteProgram(riscVfunction);
            procedure(riscVfunction, isfloat);
            return;
        }
        // 进行分配
        allocate();

        // 对于非浮点寄存器，根据实际需要调整寄存器数量
        if (!isfloat) {
            K = 7; // 如果是整型寄存器，设置为 7 个
            int maxnum = maxUsePhyA.get(riscVfunction);
            if (maxnum < indexMaxA) {
                K += (indexMaxA - maxnum); // 根据需要调整寄存器数量
            }
        } else {
            K = 12; // 浮点寄存器使用 12 个
            int maxnum = maxUseFPhyA.get(riscVfunction);
            if (maxnum < indexMaxA) {
                K += (indexMaxA - maxnum); // 根据需要调整寄存器数量
            }
        }

        // 清空一部分数据，但保留干涉图
        //只清空工作表、着色信息，但是保留干涉图。这是为了适应不同的寄存器数进行第二次分配时可以重复利用现有的数据。
        clear(Other);
        //为了处理溢出的变量时进行重复分配。这种过程属于典型的 Chaitin/Briggs 的寄存器分配器实现方式：
        //第一次：全量清空。进行活跃变量分析。构建干涉图。进行着色。溢出的需要重写代码，再递归。
        //第二次：清空一部分数据。再根据不同的数据设置不同的寄存器数。再进行干涉图重建。再进行着色。

        buildAndProcessGraph(riscVfunction,isfloat,false);

        // 如果有溢出的节点，重写程序并递归处理
        if (!spilledNodes.isEmpty()) {
            rewriteProgram(riscVfunction);
            procedure(riscVfunction, isfloat);
            return;
        }

        // 进行最终的寄存器分配
        allocate();
    }

    private void buildAndProcessGraph(RISCVfunction function, boolean isFloat, boolean isFirstStage) {
        // 构建寄存器干涉图（是否使用浮点寄存器）
        buildGraph(function, isFloat, isFirstStage);
        // 构建工作列表
        makeWorkList(isFirstStage);
        // 循环进行简化和溢出选择直到工作列表为空
        processWorkLists();
        // 执行着色过程
        assignColors(function, isFloat, isFirstStage);
    }

    private void processWorkLists() {
        while (!(simWorkList.isEmpty() && spillWorkList.isEmpty())) {
            if (!simWorkList.isEmpty()) {
                // 执行简化步骤
                simplify();
            } else {
                // 选择溢出节点进行溢出处理
                selectSpill();
            }
        }
    }

    //分析活跃变量
    public void analyzeLive(RISCVfunction riscVfunction,boolean isfloat){
        //统计每条指令的UD链
        analyzeRegisterUsage(riscVfunction, isfloat);
        //基本块间 的 liveIn liveOut
        analyzeBlock(riscVfunction);
        //每条指令级别的活性 信息推导
        analyzeInstInOut(riscVfunction, isfloat);
        //处理函数调用现场保存寄存器
        processCallSavedRegisters(riscVfunction);
        //dealWithST(riscVfunction);
    }

    private void analyzeRegisterUsage(RISCVfunction objFunction, boolean isFloat) {

        //初始化当前寄存器的最大使用数量
        maxUsePhyA.put(objFunction, 9);
        maxUseFPhyA.put(objFunction, 9);

        for (RISCVblock riscvBlock : objFunction.getBlocks()) {
            blockClearRegs(riscvBlock, All);
            //收集当前指令使用的寄存器
            for (RISCVinst instr : riscvBlock.getInstructionlist()) {
                for (RISCVreg regUse : instr.getRegUse()) {
                    analyzeRegisters(regUse, 1, riscvBlock, allOperands, objFunction, isFloat);
                }
                //收集当前指令定义的寄存器
                RISCVreg regDef = instr.getReg();
                analyzeRegisters(regDef, 0, riscvBlock, allOperands, objFunction, isFloat);
            }
        }
    }

    // 分析函数中的每个基本块，直到没有变化为止
    private void analyzeBlock(RISCVfunction objFunction) {

        boolean changed;
        do {
            // 清空已进行深度优先搜索 (DFS) 的基本块集合
            hasBeenDfs.clear();
            changed = dfs(objFunction.getExitBlock());
        } while (changed);
    }

    // 深度优先搜索 (DFS) 基本块
    private boolean dfs(RISCVblock riscvBlock) {
        //System.out.println(1);
        // 如果该基本块已经被访问过，跳过
        if (hasBeenDfs.contains(riscvBlock) || riscvBlock == null) {
            return false;
        }
        ArrayList<RISCVreg> inBackup = new ArrayList<>(liveInsReg.get(riscvBlock));

        // 将当前基本块标记为已访问
        hasBeenDfs.add(riscvBlock);

        // 计算当前基本块的 live-in 和 live-out 集合，并检查是否有变化
        boolean blockChanged = computeLiveInOut(riscvBlock);

        // 对当前基本块的前驱块递归执行 DFS，如果前驱块有变化，当前块也认为发生变化
        for (RISCVblock preBlock : riscvBlock.getPrelist()) {
            boolean preBlockChanged = dfs(preBlock);
            blockChanged |= preBlockChanged;  // 如果前驱块有变化，则当前块也视为变化
        }

        return blockChanged;  // 返回是否发生了变化
    }

    // 计算基本块的 live-in 和 live-out 集合
    private boolean computeLiveInOut(RISCVblock riscvBlock) {
        // 备份当前基本块的 live-in 集合
        ArrayList<RISCVreg> inBackup = new ArrayList<>(liveInsReg.get(riscvBlock));

        // 清空当前基本块的 live-out 集合
        blockClearRegs(riscvBlock, Lout);

        // 更新当前基本块的 live-out 集合，将所有后继块的 live-in 集合中的寄存器加入 live-out
        for (RISCVblock nextBlock : riscvBlock.getNextlist()) {
            for (RISCVreg reg : liveInsReg.get(nextBlock)) {
                // 如果寄存器不在 live-out 中，加入到 live-out
                if (!liveOutsReg.get(riscvBlock).contains(reg)) {
                    liveOutsReg.get(riscvBlock).add(reg);
                }
            }
        }

        // 清空当前基本块的 live-in 集合
        blockClearRegs(riscvBlock, Lin);

        // 将当前基本块使用的寄存器（UseReg）加入 live-in 集合
        liveInsReg.get(riscvBlock).addAll(UseReg.get(riscvBlock));

        // 将所有 live-out 中的寄存器加入 live-in 中（去重）
        for (RISCVreg reg : liveOutsReg.get(riscvBlock)) {
            if (!liveInsReg.get(riscvBlock).contains(reg)) {
                liveInsReg.get(riscvBlock).add(reg);
            }
        }

        // 从 live-in 中移除当前基本块定义的寄存器（DefReg）
        liveInsReg.get(riscvBlock).removeIf(DefReg.get(riscvBlock)::contains);

        // 检查 live-in 是否发生了变化
        boolean theSame = inBackup.size() == liveInsReg.get(riscvBlock).size();
        if (theSame) {
            // 如果两个集合的大小相同，检查集合的内容是否完全一致
            for (RISCVreg reg : inBackup) {
                if (!liveInsReg.get(riscvBlock).contains(reg)) {
                    theSame = false;
                    break;
                }
            }
        }

        // 如果 live-in 集合没有变化，返回 false；否则，返回 true
        return !theSame;
    }


    private void analyzeInstInOut(RISCVfunction objFunction, boolean isFloat) {
        for (RISCVblock riscvBlock : objFunction.getBlocks()) {
            //从块尾开始
            RISCVinst tmpInst = riscvBlock.getInstructionlist().getLast();

            while (tmpInst != null) {
                //如果是块的第一条指令 直接初始化liveIn = block 的 liveIn
                if (getPreInstr(tmpInst, riscvBlock.getInstructionlist()) == null) {
                    //更新当前的活跃变量
                    instrClearRegs(tmpInst);
                    tmpInst.getLive().addAll(liveInsReg.get(riscvBlock));
                    //用于建图
                    blockLocalInterfere.get(riscvBlock).add(liveInsReg.get(riscvBlock));
                    break;
                }

                //根据公式计算 block 的 liveout - def -> livein
                LinkedList<RISCVreg> tmpIn = new LinkedList<>(liveOutsReg.get(riscvBlock));
                tmpIn.remove(tmpInst.getReg());

                //加入USE
                for (RISCVreg reg : tmpInst.getRegUse()) {
                    if (!tmpIn.contains(reg)) {
                        if (isFloat) {
                            if (reg instanceof virtualFReg) {
                                tmpIn.add(reg);
                            }
                        } else {
                            if (reg instanceof virtualReg) {
                                tmpIn.add(reg);
                            }
                        }
                    }
                }
                //保存指令的liveIn集合
                blockLocalInterfere.get(riscvBlock).add(tmpIn);
                instrClearRegs(tmpInst);
                tmpInst.getLive().addAll(tmpIn);

                //更新liveout 为上一条指令作准备
                liveOutsReg.replace(riscvBlock, tmpIn);
                //向上递归
                tmpInst = getPreInstr(tmpInst, riscvBlock.getInstructionlist());
            }
        }
    }

    //获取当前指令的上一条指令
    private RISCVinst getPreInstr(RISCVinst instr, LinkedList<RISCVinst> list) {
        int index = list.indexOf(instr);
        if (index == 0) {
            return null;
        } else {
            return list.get(index - 1);
        }
    }

    //清空活跃变量
    private void instrClearRegs(RISCVinst instr) {
        instr.getLive().clear();
    }

    //分析在函数 call的时候那些需要变动

    private void processCallSavedRegisters(RISCVfunction objFunction) {
        clear(ST);//清空call-save 标记集合
        //将块入口处活跃寄存器加入 S 集合，需要进行保存的寄存器
        collectCallSavedRegisters(objFunction);
        //处理不需要保存的寄存器
        determineTemporaryRegisters();
    }

    private void collectCallSavedRegisters(RISCVfunction objFunction) {
        for (RISCVblock block : objFunction.getBlocks()) {
            SOperands.addAll(liveInsReg.get(block));
            for (RISCVinst instr : block.getInstructionlist()) {
                RISCVinst prev = getPreInstr(instr, block.getInstructionlist());
                if (prev instanceof RISCVcall) {
                    SOperands.addAll(instr.getLive());
                }
            }
        }
    }

    private void determineTemporaryRegisters() {
        for (RISCVoperand operand : allOperands) {
            if (!SOperands.contains(operand)) {
                TOperands.add(operand);
            }
        }
    }


    //
    private void analyzeRegisters(RISCVreg reg, int isUse, RISCVblock riscvBlock, HashSet<RISCVoperand> all, RISCVfunction objFunction, boolean isFloat) {
        if (reg instanceof physicalReg && ((physicalReg) reg).getIndex() >= indexMinA && ((physicalReg) reg).getIndex() <= indexMaxA && ((physicalReg) reg).getIndex() > maxUsePhyA.get(objFunction)) {
            maxUsePhyA.put(objFunction, ((physicalReg) reg).getIndex());
        } else if (reg instanceof physicalFReg && ((physicalFReg) reg).getIndex() >= indexMinA && ((physicalFReg) reg).getIndex() <= indexMaxA && ((physicalFReg) reg).getIndex() > maxUseFPhyA.get(objFunction)) {
            maxUseFPhyA.put(objFunction, ((physicalFReg) reg).getIndex());
        }
        if (isFloat) {
            if (reg instanceof virtualFReg) {
                all.add(reg);
                if (containsReg(riscvBlock, reg) && isUse == 1) {
                    UseReg.get(riscvBlock).add(reg);
                } else if (containsReg(riscvBlock, reg) && isUse == 0) {
                    DefReg.get(riscvBlock).add(reg);
                }
            }
        } else {
            if (reg instanceof virtualReg) {
                all.add(reg);
                if (containsReg(riscvBlock, reg) && isUse == 1) {
                    UseReg.get(riscvBlock).add(reg);
                } else if (containsReg(riscvBlock, reg) && isUse == 0) {
                    DefReg.get(riscvBlock).add(reg);
                }
            }
        }
    }


    //isFirstStage 表示是否在第一阶段 call-save 构建
    public void buildGraph(RISCVfunction riscVfunction,boolean isfloat,boolean isFirstStage){
        for (RISCVblock riscvBlock : riscVfunction.getBlocks()) {
            //每个块单独记录当前 块寄存器中寄存器的使用频率
            HashMap<RISCVreg, Integer> regFrequency = new HashMap<>();
            //遍历所有的指令
            for (RISCVinst tmpInst : riscvBlock.getInstructionlist()) {
                //统计所有 usereg
                for (RISCVreg reg : tmpInst.getRegUse()) {
                    multiResult(regFrequency, reg, isfloat, isFirstStage);
                }
                //统计 defreg
                multiResult(regFrequency, tmpInst.getReg(), isfloat, isFirstStage);
            }

            //根据评论统计溢出代价 越频繁使用 越深的块权重越高
            for (RISCVreg reg : regFrequency.keySet()) {
                int value = regFrequency.get(reg);
                //int value2 = reg.getUseFrequency();
                spillWeight.compute(reg, (k, oldVal) -> {
                    if (oldVal == null) {
                        oldVal = 0; // 初始值
                    }
                    return oldVal + 5 * value * (riscvBlock.getdepth() + 1);
                });
            }
        }

        //构建干涉边 块入口活跃寄存器之间相互干涉
        for (RISCVblock riscvBlock : riscVfunction.getBlocks()) {
            //处理 livein 寄存器里面两两之间的干涉关系
            for (int i = 0; i < liveInsReg.get(riscvBlock).size(); i++) {
                for (int j = i + 1; j < liveInsReg.get(riscvBlock).size(); j++) {
                    multiStage(liveInsReg.get(riscvBlock).get(i), liveInsReg.get(riscvBlock).get(j), isFirstStage);
                }
            }
            //指令级别的干涉 （局部干涉）
            for (LinkedList<RISCVreg> regList : blockLocalInterfere.get(riscvBlock)) {
                for (int i = 0; i < regList.size(); i++) {
                    for (int j = i + 1; j < regList.size(); j++) {
                        multiStage(regList.get(i), regList.get(j), isFirstStage);
                    }
                }
            }
        }
    }

    //统计寄存器使用频率
    private void multiResult(HashMap<RISCVreg, Integer> regFrequency, RISCVreg reg, boolean isFloat, boolean isFirstStage) {
        if (isFloat) {
            //浮点数寄存器
            if (reg instanceof virtualFReg) {
                if (isFirstStage) {
                    if (SOperands.contains(reg)) {
                        helpBuild(regFrequency, reg);
                    }
                } else {
                    if (TOperands.contains(reg)) {
                        helpBuild(regFrequency, reg);
                    }
                }
            }
        } else {
            if (reg instanceof virtualReg) {
                if (isFirstStage) {
                    if (SOperands.contains(reg)) {
                        helpBuild(regFrequency, reg);
                    }
                } else {
                    if (TOperands.contains(reg)) {
                        helpBuild(regFrequency, reg);
                    }
                }
            }
        }
    }

    //初始化图结构  更新该寄存器使用频率
    private void helpBuild(HashMap<RISCVreg, Integer> regFrequency, RISCVreg reg) {
        degree.put(reg, 0);
        adjList.put(reg, new HashSet<>()); //初始化邻接集合
        regFrequency.merge(reg, 1, Integer::sum);  // 如果是 第一次出现 是 1 否则 +1求和
    }

    //两个寄存器都属于 s / t 建立干涉边
    private void multiStage(RISCVreg leftReg, RISCVreg rightReg, boolean isFirstStage) {
        if (isFirstStage) {
            //第一阶段 考虑 集合S
            if (SOperands.contains(leftReg) && SOperands.contains(rightReg)) {
                AddEdge(leftReg, rightReg);
            }
        } else {
            //第二阶段 考虑集合 T
            if (TOperands.contains(leftReg) && TOperands.contains(rightReg)) {
                AddEdge(leftReg, rightReg);
            }
        }
    }

    //添加干涉边
    private void AddEdge(RISCVoperand left, RISCVoperand right) {
        if (!adjSet.contains(new Edge<>(left, right)) && !left.equals(right)) {
            //避免重复进行加边操作的
            adjSet.add(new Edge<>(left, right));
            adjSet.add(new Edge<>(right, left));
            //如果需要进行染色
            if (left.isColored()) {
                //确保 left 在邻接表中存在
                adjList.putIfAbsent(left, new HashSet<>());
                adjList.get(left).add(right);
                //变动 left的度数
                int currentValue = degree.getOrDefault(left, 0);
                degree.put(left, currentValue + 1);
            }
            if (right.isColored()) {
                adjList.putIfAbsent(right, new HashSet<>());
                adjList.get(right).add(left);
                int currentValue = degree.getOrDefault(right, 0);
                degree.put(right, currentValue + 1);
            }
        }
    }

    //将活跃寄存器放入简化或 溢出工作列表
    public void makeWorkList(boolean isFirstStage){
        HashSet<RISCVoperand> SorT;
        //依据 选择是操作 S集合还是T集合
        if (isFirstStage) {
            SorT = SOperands;
        } else {
            SorT = TOperands;
        }

        for (RISCVoperand operand : SorT) {
            //不存在的跳过
            if (!degree.containsKey(operand)) {
                continue;
            }
            //如果度数 >= k说明此时无法完成着色，放入溢出列表
            if (degree.get(operand) >= K) {
                spillWorkList.add(operand);
            } else {
                //否则放入简化列表
                simWorkList.add(operand);
            }
        }
    }

    public void simplify(){
        //从简化图
        Iterator<RISCVoperand> iterator = simWorkList.iterator();
        RISCVoperand operand = iterator.next();
        //处理当前寄存器 将选择的低度数节点移动到 stackForSelect
        simWorkList.remove(operand);
        stackForSelect.push(operand);
        //获取该结点邻接节点中未被简化的
        HashSet<RISCVoperand> result = Adjacent(operand);
        //所有未被简化的 的度数减一
        for (RISCVoperand objOperand : result) {
            decrementDegree(objOperand);
        }
    }

    private HashSet<RISCVoperand> Adjacent(RISCVoperand operand) {
        HashSet<RISCVoperand> result = new HashSet<>(adjList.get(operand));
        //如果已经在 stackForSelect 就不需要进行处理了
        for (RISCVoperand objOperand : stackForSelect) {
            result.remove(objOperand);
        }
        return result;
    }

    private void decrementDegree(RISCVoperand operand) {
        //当前度数 自减
        degree.put(operand, degree.get(operand) - 1);
        //之前存在  溢出列表中的寄存器随着简化图可能可以简化到 简化列表中
        if (degree.get(operand) == K - 1) {
            spillWorkList.remove(operand);
            simWorkList.add(operand);
        }
    }

    private double getMaxForSpill(RISCVoperand operand) {
        //一种度量方式 度数 / 溢出权重
        return ((double) degree.getOrDefault(operand, 0)) / spillWeight.getOrDefault(operand, 0);
    }

    public void selectSpill(){
        boolean first = true;
        RISCVoperand spillOperand = null;
        for (RISCVoperand operand : spillWorkList) {
            if (first) {
                spillOperand = operand;
                first = false;
            } else {
                if (getMaxForSpill(spillOperand) < getMaxForSpill(operand)) {
                    spillOperand = operand;
                }
            }
        }

        //转移
        spillWorkList.remove(spillOperand);
        simWorkList.add(spillOperand);
    }

    public void assignColors(RISCVfunction riscVfunction,
                             boolean isfloat,
                             boolean isFirstStage){
        //一直处理简化栈 直到栈为空
        while (!stackForSelect.isEmpty()) {
            //取出一个
            RISCVoperand operand = stackForSelect.pop();
            HashSet<Integer> baseOkColors = new HashSet<>();
            if (isfloat) {
                if (isFirstStage) {
                    // fs0 ~ fs11
                    baseOkColors.addAll(Arrays.asList(8, 9, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27));
                } else {
                    //ft0~ft11
                    baseOkColors.addAll(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 28, 29, 30, 31));

                    int maxUseA = maxUseFPhyA.get(riscVfunction);
                    for (int i = maxUseA + 1; i <= indexMaxA; i++) {
                        baseOkColors.add(i);
                    }
                }
            } else {
                if (isFirstStage) {
                    // s0 ~ s11
                    baseOkColors.addAll(Arrays.asList(8, 9, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27));
                } else {
                    //t0 ~ t6
                    baseOkColors.addAll(Arrays.asList(5, 6, 7, 28, 29, 30, 31));
                    int maxUseA = maxUsePhyA.get(riscVfunction);
                    for (int i = maxUseA + 1; i <= indexMaxA; i++) {
                        baseOkColors.add(i);
                    }
                }
            }

            //遍历邻接节点 移除已经占用的颜色
            for (RISCVoperand objOperand : adjList.get(operand)) {
                if (coloredNodes.contains(objOperand)) {
                    baseOkColors.remove(color.get(objOperand));
                }
            }

            //如果没有颜色分配了，溢出
            if (baseOkColors.isEmpty()) {
                spilledNodes.add(operand);
            } else {
                //分配颜色
                coloredNodes.add(operand);
                int colorValue = baseOkColors.iterator().next();
                baseOkColors.remove(colorValue);
                color.put(operand, colorValue);
            }
        }
    }

    private void generateMemoryInstruction(RISCVoperand operand, int offset,
                                           String opType, RISCVfunction function,
                                           RISCVinst instr, boolean isLoad) {
        if (offset >= -2048 && offset <= 2047) {
            createSimpleMemoryOp(operand, offset, opType, function, instr, isLoad);
        } else {
            createComplexMemoryOp(operand, offset, opType, function, instr, isLoad);
        }
    }
    private void createSimpleMemoryOp(RISCVoperand operand, int offset,
                                      String opType, RISCVfunction function,
                                      RISCVinst instr, boolean isLoad) {
        RISCVoperand baseReg = initReg.SP;
        RISCVimm imm = new RISCVimm(offset, true);

        if (isLoad) {
            RISCVload load = new RISCVload(Arrays.asList(operand, baseReg, imm), opType);
            function.addInstBefore(instr, load);
        } else {
            RISCVstore store = new RISCVstore(Arrays.asList(operand, baseReg, imm), opType);
            function.addInstAfter(instr, store);
        }
    }

    private void createComplexMemoryOp(RISCVoperand operand, int offset,
                                       String opType, RISCVfunction function,
                                       RISCVinst instr, boolean isLoad) {
        // 创建临时寄存器
        virtualReg tempReg = new virtualReg();

        // 加载大立即数到临时寄存器
        RISCVmove move = new RISCVmove(Arrays.asList(tempReg, new RISCVimm(offset, false)));

        // 计算实际地址: SP + tempReg
        RISCVbinary add = new RISCVbinary("add", Arrays.asList(tempReg, initReg.SP, tempReg));

        // 创建内存操作指令
        RISCVimm zeroImm = new RISCVimm(0, true);
        RISCVinst memoryOp;

        if (isLoad) {
            memoryOp = new RISCVload(Arrays.asList(operand, tempReg, zeroImm), opType);
        } else {
            memoryOp = new RISCVstore(Arrays.asList(operand, tempReg, zeroImm), opType);
        }

        // 插入指令序列
        if (isLoad) {
            function.addInstBefore(instr, move);
            function.addInstBefore(instr, add);
            function.addInstBefore(instr, memoryOp);
        } else {
            function.addInstAfter(instr, move);
            function.addInstAfter(move, add);
            function.addInstAfter(add, memoryOp);
        }
    }

    private void spillsapcealloc(RISCVfunction riscVfunction,HashSet<RISCVinst> needRewrite){
        // 当前的栈偏移量，初始化为函数的栈大小
        int nowOffset = riscVfunction.getStacksize();
        for (RISCVblock riscvBlock : riscVfunction.getBlocks()) {
            // 遍历基本块中的每条指令
            for (RISCVinst instr : riscvBlock.getInstructionlist()) {
                // 获取当前指令使用的寄存器，并移除当前指令定义的寄存器
                ArrayList<RISCVoperand> tmp = new ArrayList<>(instr.getRegUse());
                tmp.remove(instr.getReg());  // 移除当前指令的寄存器定义
                tmp.add(instr.getReg());     // 重新添加该寄存器

                // 遍历当前指令使用的所有寄存器
                for (RISCVoperand operand : tmp) {
                    // 如果该寄存器是溢出寄存器（spill），则需要对指令进行重写
                    if (spilledNodes.contains(operand)) {
                        needRewrite.add(instr);

                        // 如果该操作数没有被分配溢出空间（spillspace），则为其分配空间
                        if (operand.getSpillspace() == -1) {
                            operand.setSpillspace(nowOffset);  // 设置溢出空间位置
                            nowOffset += 8;  // 偏移量增加8字节（每个寄存器大小）
                            riscVfunction.addAllocSize(8);  // 增加函数分配的栈空间
                        }
                    }
                }
            }
        }
    }

    // rewriteProgram 方法负责重写给定函数中的所有指令，特别是处理由于寄存器溢出（spill）而需要重新加载和存储的情况
    public void rewriteProgram(RISCVfunction riscVfunction){
        // 用于存储需要重写的指令
        HashSet<RISCVinst> needRewrite = new HashSet<>();

        // 遍历函数的所有基本块
        spillsapcealloc(riscVfunction,needRewrite);

        // 处理需要重写的指令
        for (RISCVinst instr : needRewrite) {
            // 遍历指令的所有使用寄存器
            for (RISCVoperand regUse : instr.getRegUse()) {
                // 如果使用的寄存器是溢出寄存器
                if (spilledNodes.contains(regUse)) {
                    // 如果是浮点寄存器，则需要加载浮点数寄存器
                    if (regUse instanceof virtualFReg) {
                        initReg.fphycounter++;  // 增加浮点数寄存器计数器（原因：浮点数寄存器在处理时有特殊要求）
                        generateMemoryInstruction(regUse, regUse.getSpillspace(), "fld", riscVfunction, instr,true);
                    } else {
                        // 否则为整数寄存器，插入加载指令
                        generateMemoryInstruction(regUse, regUse.getSpillspace(), "ld", riscVfunction, instr,true);
                    }
                }
            }

            // 获取指令的定义寄存器
            RISCVoperand regDef = instr.getReg();

            // 如果定义的寄存器是溢出寄存器，插入存储指令
            if (spilledNodes.contains(regDef)) {
                // 如果是浮点寄存器，插入浮点存储指令
                if (regDef instanceof virtualFReg) {
                    // 此处不自增的原因 类似 a = a + 1
                    generateMemoryInstruction(regDef,regDef.getSpillspace(), "fsd", riscVfunction, instr,false);
                } else {
                    // 否则为整数寄存器，插入存储指令
                    generateMemoryInstruction(regDef, regDef.getSpillspace(), "sd", riscVfunction, instr,false);
                }
            }
        }
    }

    public void allocate(){
        for (HashMap.Entry<RISCVoperand, Integer> entry : color.entrySet()) {
            RISCVoperand key = entry.getKey();
            key.setColor(entry.getValue());
        }
    }
    public  void finalAllocate(RISCVfunction function,boolean isFloat){
            for (RISCVblock riscvBlock : function.getBlocks()) {
                for (RISCVinst instr : riscvBlock.getInstructionlist()) {
                    ArrayList<RISCVreg> instrReg = new ArrayList<>(instr.getRegUse());
                    for (RISCVreg reg : instrReg) {
                        helpAllocate(instr, reg, isFloat);
                    }
                    RISCVreg reg = instr.getReg();
                    helpAllocate(instr, reg, isFloat);
                }
            }
    }

    private void helpAllocate(RISCVinst instr, RISCVreg reg, boolean isFloat) {
        if (isFloat) {
            if (reg instanceof virtualFReg) {
                instr.replaceReg(reg, phyfRegs.get(reg.getColor()));
            }
        } else {
            if (reg instanceof virtualReg) {
                instr.replaceReg(reg, phyRegs.get(reg.getColor()));
            }
        }
    }

    //ywq todo
    public List<IR_BaseBlock> getImmediaSuccessors (IR_BaseBlock block) {
        List<IR_BaseBlock> immedia_successors = new ArrayList<>();
        return immedia_successors;
    }
}
